#ifndef _ONEWAYCIRLINKLIST_H_
#define _ONEWAYCIRLINKLIST_H_
#include"Public.h"
#include"Node in linklist.h"
#include<cstdlib>
#include<iostream>

using namespace std;

template <typename ElemType>
class OneWayCirLinkList {

	typedef Node<ElemType> *Position;

public:
	OneWayCirLinkList();
	~OneWayCirLinkList();

	bool isEmpty() const;
	bool isLast(const Position p) const;

	Position Find(const ElemType key) const {
		Position temp = m_pHead;

		while (temp->getData() != key && temp->getNext() != m_pHead) {
			temp = temp->getNext();
		}
		if (temp->getData() == key)
			return temp;
		else
			return NULL;
	}
	Position FindPrevious(const ElemType key) const {
		Position cur = m_pHead;

		do {
			if (cur->getNext()->getData() == key)
				return cur;
			cur = cur->getNext();
		} while (cur != m_pHead);

		cout << "Can't find this node!" << endl;
		return NULL;

	}
	Position FindPrevious(const Position cur) const {
		Position cur = m_pHead;
		while (cur->getNext() != cur) {
			cur = cur->getNext();
		}
		return cur;
	}

	Status Delete(const ElemType key);
	Status Delete(Position cur);

	Status Insert(const ElemType key);
	Status Insert(const ElemType key, const Position p);
	Status Insert(const int sort_way, const ElemType key);
	
	Status show_data() const;
	Status addLength();
	Status cutLength();
	int getLength() const;

private:
	Position m_pHead;
	int  m_iLength;

};

template <typename ElemType>
OneWayCirLinkList<ElemType>::OneWayCirLinkList() :m_iLength(0), m_pHead(NULL) {
}

template <typename ElemType>
OneWayCirLinkList<ElemType>::~OneWayCirLinkList() {
	if (!isEmpty()) {
		Position cur = m_pHead, next = cur->getNext();
		if (cur == next) {
			delete cur;
			cur = next = NULL;
		}
		do {
			delete cur;
			cur = next;
			next = next->getNext();
		} while (next != m_pHead);
		cur = next = m_pHead = NULL;
	}
}

template <typename ElemType>
bool OneWayCirLinkList<ElemType>::isEmpty() const  {
	return m_pHead == NULL;
}

template <typename ElemType>
bool OneWayCirLinkList<ElemType>::isLast(const Position p) const {
	return p->getNext() == m_pHead;
}

template <typename ElemType>
Status OneWayCirLinkList<ElemType>::Delete(const ElemType key) {
	Position temp, p = m_pHead;

	while (p->getData() != key && p->getNext() != m_pHead) {
		temp = p;
		p = p->getNext();
	}
	if (p->getNext() == m_pHead) {
		cout << "Can't find this node! Failed!" << endl;
		return ERROR;
	}
	else {
		temp->setNext(p->getNext());
		delete p;
		p = NULL;
	}
	cutLength();
	return OK;
}

template <typename ElemType>
Status OneWayCirLinkList<ElemType>::Delete(Position cur) {
	Position temp = m_pHead;
	do {
		if (temp->getNext() == cur) {
			temp->setNext(cur->getNext());
			delete cur;
			cur = NULL;
			cout << "\nDONE!" << endl;
			return OK;
		}
		temp = temp->getNext();
	} while (temp != m_pHead);
	cout << "\nCan't find this node!Failed!" << endl;
	return ERROR;
}

template <typename ElemType>
Status OneWayCirLinkList<ElemType>::Insert(const ElemType key) {
	Node<ElemType> *NewNode = new Node<ElemType>;
	if (NewNode == NULL) {
		perror("Failed to reallocate memory!\nCan't add new element!\n");
		exit(VOERFLOW);
	}
	else {
		Position m_pTail = m_pHead;
		while (m_pTail->getNext() != m_pHead) {
			m_pTail = m_pTail->getNext();
		}
		addLength();
		m_pTail->setNext(NewNode);
		NewNode->setData(key);
		NewNode->setNext(m_pHead);
	}
	return OK;
}

template <typename ElemType>
Status OneWayCirLinkList<ElemType>::Insert(const ElemType key, const Position p) {
	Node<ElemType> *NewNode = new Node<ElemType>;
	if (NewNode == NULL) {
		perror("Failed to reallocate memory!\nCan't add new element!\n");
		return ERROR;
	}
	else {

		NewNode->setData(key);
		NewNode->setNext(p->getNext());
		p->setNext(NewNode);
		addLength();
	}
	return OK;
}

template <typename ElemType>
Status OneWayCirLinkList<ElemType>::Insert(const int sort_way, const ElemType key) {
	Position temp = new Node<ElemType>;
	if (temp == NULL) {
		perror("Failed to reallocate memory!\nCan't add new element!\n");
		return ERROR;
	}
	temp->setData(key);
	temp->setNext(NULL);

	if (isEmpty()) {
		m_pHead = temp;
		temp->setNext(m_pHead);
		addLength();
		return ERROR;
	}
	Position pre = m_pHead, after = pre->getNext();
	if (sort_way == up) {
		do {
			if (pre->getData() <= key && after->getData() >= key
				|| (pre->getData() < key && after->getData() < key && after == m_pHead)
				|| (pre->getData() > key && after->getData() > key && after == m_pHead)) {
				pre->setNext(temp);
				temp->setNext(after);
				if (pre->getData() > key && after->getData() > key) {
					m_pHead = temp;
				}
				addLength();
				return ERROR;
			}
			else {
				pre = after;
				after = after->getNext();
			}
		} while (pre != m_pHead);
	}
	else if (sort_way == down) {
		do {
			if ((pre->getData() >= key && after->getData() <= key)
				|| (pre->getData() < key && after->getData() < key)
				|| (pre->getData() > key && after->getData() > key)) {
				pre->setNext(temp);
				temp->setNext(after);
				if (pre->getData() < key && after->getData() < key) {
					m_pHead = temp;
				}
				addLength();
				return ERROR;
			}
			else {
				pre = after;
				after = after->getNext();
			}
		} while (pre != m_pHead);
	}
	return OK;
}

template <typename ElemType>
Status OneWayCirLinkList<ElemType>::show_data() const {
	Position temp = m_pHead;
	cout << "\n------------------- Data -------------------:" << endl;
	do {
		cout << temp->getData() << ' ';
		temp = temp->getNext();
	} while (temp != m_pHead);
	cout << "Total: " << getLength() << endl;
	return OK;
}

template <typename ElemType>
Status OneWayCirLinkList<ElemType>::addLength(){
	++m_iLength;
	return OK;
}

template <typename ElemType>
Status OneWayCirLinkList<ElemType>::cutLength() {
	--m_iLength;
	return OK;
}

template <typename ElemType>
int OneWayCirLinkList<ElemType>::getLength() const {
	return m_iLength;
}

#endif

